﻿#include <iostream>

#define point_num 7                 // 顶点数
#define infinity  999999            // 表示最大

namespace dijkstra_dynamic
{

int metrix[point_num][point_num] = {
        {infinity, 12, infinity, infinity, infinity, 16, 14},
        {12, 10, infinity, infinity, infinity, 7, infinity},
        {infinity, 10, infinity, 3, 5, 6, infinity},
        {infinity, infinity, 3, infinity, 4, infinity, infinity},
        {infinity, infinity, 5, 4, infinity, 2, 8},
        {16, 7, 6, infinity, 2, infinity, 9},
        {14, infinity, infinity, infinity, 8, 9, infinity},
};

// 计算两个点的直连距离，不直连返回infinity
int calc_vertex_distance(int vertex1, int vertex2)
{
    return metrix[vertex1][vertex2];
}

/*
    * Dijkstra最短路径
    *
    * 参数说明：
    *     G     -- 图
    *     begin -- 起始顶点
    *     goal  -- 目标顶点
    *     path  -- 路径
    *     dist  -- 数组，保存到begin的最短路径
    */
void dijkstra_dynamic(int begin, int goal, int path[])
{
    int scand_list[point_num];      // scand_list[i] = 0未遍历过，= 1已遍历过
    int dist[point_num];

    // 初始化
    for (int i = 0; i < point_num; i++)
    {
        scand_list[i] = 0;              // 顶点i的最短路径还没获取到。
        path[i] = 0;                    // 顶点i的前驱顶点为0。
        dist[i] = calc_vertex_distance(begin, i);   // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }

    // 对"顶点vs"自身进行初始化
    scand_list[begin] = 1;
    dist[begin] = 0;

    // 遍历除begin以外的所有点，更新dist数组
    for (int i = 1; i < point_num; i++)
    {
        // 找出当前最近的那个点，对它进行递归
        int min = infinity;
        int next_vertex;
        for (int j = 0; j < point_num; j++)
        {
            if (scand_list[j] == 0 && dist[j] < min)
            {
                min = dist[j];
                next_vertex = j;
            }
        }

        // 最短路径的点就是目标点，不再需要遍历
        if (next_vertex == goal)
            return;

        // 设置已经被遍历
        scand_list[next_vertex] = 1;

        // 如果经过next_vertex到达目标比直接到达更近，更新之
        for (int j = 0; j < point_num; j++)
        {
            int temp = calc_vertex_distance(next_vertex, j) + min;
            if (scand_list[j] == 0 && (temp < dist[j]))
            {
                dist[j] = temp;
                path[j] = next_vertex;
            }
        }
    }
}

}

int main(int argn, char* argv[])
{
    int path[point_num];
    int begin = 0;
    int goal = 3;
    dijkstra_dynamic::dijkstra_dynamic(begin, goal, path);
    
    while (goal != begin)
    {
        printf("dyn--%d\n", path[goal]);
        goal = path[goal];
    }
    
    return 0;
}